package Prim;

import java.util.Arrays;

public class myTest {
    public static void main(String[] args) {
        //测试看看图是否创建ok
        char[] data = new char[]{'A','B','C','D','E','F','G'};
        int verxs = data.length;
        //邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
        int [][]weight=new int[][]{
                {10000,5,7,10000,10000,10000,2},
                {5,10000,10000,9,10000,10000,3},
                {7,10000,10000,10000,8,10000,10000},
                {10000,9,10000,10000,10000,4,10000},
                {10000,10000,8,10000,10000,5,4},
                {10000,10000,10000,4,5,10000,6},
                {2,3,10000,10000,4,6,10000},};

        //创建MGraph对象
        MyMGraph graph = new MyMGraph(verxs);
        //创建一个MinTree对象
        MyMinTree minTree = new MyMinTree();
        minTree.createGraph(graph,verxs,data,weight);
        minTree.showGraph(graph);
        minTree.primAl(graph,'E');
    }
}
class MyMinTree {
    public void createGraph(MyMGraph graph, int verxs, char[] data, int[][] weight) {
        int i, j;
        for(i = 0; i < verxs; i++) {//顶点
            graph.data[i] = data[i];
            for(j = 0; j < verxs; j++) {
                graph.weight[i][j] = weight[i][j];
            }
        }
    }
    public void showGraph(MyMGraph graph){
        for(int[] i:graph.weight){
            System.out.println(Arrays.toString(i));
        }

    }
    public void primAl(MyMGraph graph,char v){
        int[] gTag = new int[graph.verxs];
        for(int i = 0;i< gTag.length;i++){
            if(graph.data[i] == v){
                gTag[i] = 1;
            }
        }
        System.out.println(Arrays.toString(gTag));
        int h1 = -1;
        int h2 = -1;
        int minkey = 102400;
        for (int k = 0; k < graph.verxs -1; k++){
            h1 = -1;
            h2 = -1;
            // 找到连通的最小的边
            for(int i = 0; i < graph.verxs; i++){
                for (int j = 0; j < graph.verxs;j++){
                    if(gTag[i] == 1 && gTag[j] == 0 && graph.weight[i][j] < minkey){
                        minkey = graph.weight[i][j];
                        h1 = i;
                        h2 = j;
                    }
                }
            }
            //将当前这个结点标记为已经访问
            System.out.println( graph.data[h1] + " -> "+ graph.data[h2] + " : " +minkey);

            gTag[h2] = 1;
            //minWeight 重新设置为最大值 10000
            minkey = 10000;

        }
    }

}




class MyMGraph {
    int verxs; //表示图的节点个数
    char[] data;//存放结点数据
    int[][] weight; //存放边，就是我们的邻接矩阵

    public MyMGraph(int verxs) {
        this.verxs = verxs;
        data = new char[verxs];
        weight = new int[verxs][verxs];
    }
}

